Illustrated in FIG. 1 is a data communications network 100 including a plurality of bridges 101-120 operatively coupled in the form of a ring by network links 130. The topology of the network 100 is useful to understand the drawbacks attributable to the prior art as well as the advantages of the present invention discussed in more detailed below. Each of the bridges 101-120 includes a plurality of network ports enabled with a link management protocol to resolve transmission loops in the network 100 that can give rise to broadcast storms. The link management protocol may be selected, for example, from the group comprising the Spanning Tree Protocol (STP) standardized in International Electrical and Electronics Engineers (IEEE) standard 802.1D 2004, the Rapid Spanning Tree Protocol (RSTP) defined in IEEE standard 802.1w, and IEEE standard 802.1Q 2003 addressing the use of multiple spanning trees in virtual local area network (VLAN) bridges in accordance with the Multiple Spanning Tree Protocol (MSPT) defined in IEEE standard 802.1s, each of which is hereby incorporated by reference herein.
In accordance with the RSTP, the bridges 101-120 are adapted to exchange BPDUs protocol data unit (BPDUs) messages for purposes of determining which of the plurality of bridges is to serve as the root bridge among as well as the role of each port of every bridge. To determine the root bridge and the applicable port roles, the bridges exchange BPDU messages with priority information referred to as message priority vectors (MPVs). A bridge generally transmits BPDUs at a regular interval given by a bridge Hello time timer value, i.e., a Hello time, set forth in the RSTP standard or sends the BPDUs when a change in the spanning tree topology is initiated. A MPV has the following structure: <Root_Id, Root_Path_Cost, Designated_Bridge_ID, Designated_Port_ID, Port ID>, each of the components of the vector being well understood by those skilled in the art. Upon receipt of a BPDU, a bridge port compares the received MPV with its own priority vector referred to as a port priority vector (PPV). If the received MPV is “superior” to the PPV, i.e., numerically lower, the port's state machine computes the role of each port of every bridge, which may confirm the existing spanning tree topology or, if necessary, initiate a spanning tree topology change.
The Root bridge in the spanned tree is generally the bridge with the lowest bridge ID (BID), i.e., the lowest MAC address, and resides at the head of the spanning tree. Although, every bridge initially considers itself the root bridge, each bridge learns the identity of the bridge with the lowest BID through the exchange of BPDUs. In determining the role of the ports of the plurality of bridges, each of the ports is classified as either a root port, a designated port, a backup port, or an alternate Port. With the exception of the root bridge, every bridge has one root port, namely the port of the bridge that provides the lowest cost path to the Root Bridge. A Designated port is an interface used to send and receive frames on a specific network segment. Although the designated port may be one of a plurality ports accessible to the specific network segment, the Designated port is determined based upon the lowest root cost path. The Alternate and Backup ports provide connectivity if other network components fail. An Alternate port offers an additional path to the Root bridge beyond the path provided by a bridge's own Root port. A Backup port offers an additional path to the leaves of the spanning tree beyond the path provided by the Designated port for the network segment.
The ports of a bridge may also be characterized by one or more of a plurality of states, namely a Forwarding state, a Discarding state, and a Learning state, each of which is set forth in the 802.1D 2004 standard. In the Learning state, the port temporarily learns the identities of nodes reachable through the port but does not forward frames. In the Forwarding state, which generally follows the learning state, the bridge forwards frames in accordance with a filtering database. In the Discarding state, all traffic is dropped with the exception of control traffic at Layer 2 of the Open Systems Interconnect (OSI) reference model.
Illustrated in FIG. 2 is a message diagram representing a BPDU traffic burst in the communications network 100 of FIG. 1 as a result of a link failure. The term “traffic burst” as used herein refers to situations in which a bridge enabled with RSTP simultaneously transmits a plurality of BPDUs on one or more of its ports at the same time upon receipt of a BPDU with “superior information” on any port. “Superior Information” as used herein is defined in the 802.1D 2004 standard paragraph 17.6 entitled “Priority vector calculations.” The BPDU traffic burst of FIG. 1 represents a worst case scenario that could occur under the circumstances stated below. As a consequence of a BPDU traffic burst, the convergence of the spanning tree may be delayed.
For purposes of this example, bridge 111 has the lowest MAC address of the set of bridges 111-120 on the left side of the network 100, the bridges 112-119 have consecutively higher MAC addresses starting from bridge 112, and bridge 119 has the highest MAC address. The MAC addresses of the bridges 102-110 on the right side of the network 100 are not relevant to this discussion below. Assuming that the communications links—including link 130A—are active, the first port 111A of the bridge 111 may serve as a Root bridge while the second port 111B may serve as an Alternate port 111B. In addition, the bridges 101-120 are configured with the RSTP default values including a migrate time of 3 seconds, a bridge hello time of 2 seconds, a bridge max age of 20 seconds, a bridge forward delay of 15 seconds and a transmit hold count of 6.
Bridge 112 includes a designated port 112A for transmitting frames to the adjacent local area network (LAN) segment while bridge 111 includes an alternate port 111 providing an alternate path from the intermediate LAN segment to the root bridge.
For purposes of the following example, it is assumed that the bridge 101 is the Root bridge, bridge 102 is designated bridge for purposes of bridges 103-111, and bridge 120 is designated bridge with respect to bridges 112-119. If the communication link 130A between the bridge 120 and the root bridge 101 fails and the exchange of data terminated 202, the bridges exchange BPDUs to re-establish the appropriate propagation path in accordance with the RSTP protocol. After the failure of link 130A and the restructure of the spanning tree, all frames transmitted to the plurality of bridges 102-120 will be transmitted through the bridge 102.
Upon detection of the link failure, port 120B of bridge 120 is reclassified from a Root port to a disabled port and all root port information purged. In the absence knowledge of the root bridge 101 or the path thereto, bridge 120 believes it to be the root bridge and sends a BPDU 204 to bridge 119 announcing that bridge 120 is the new root bridge. Upon receipt of the BPDU 204 from bridge 120, bridge 119 discards its root port information and the bridge port 119B compares the received MPV with its own PPV vector. When bridge 119 determines that it has better vector, bridge 119 immediately transmits BPDUs 206 from each of its ports announcing that bridge 119 is the new root bridge. Although port 120A of bridge 120 transitions to a designated port, bridge 118 compares 207 the received MPV from bridge 119 with its own PPV vector. When bridge 118 determines that it has a superior priority vector, bridge 120 immediately transmits BPDUs 208 to its neighbors announcing that bridge 118 is the new root bridge. Port 119A of bridge 119 transitions to the designated port state and the BPDU 208 forwarded to the bridge 120.
The pattern described above is repeated many times over with each bridge from bridge 117 to bridge 111 receiving a BPDU announcing that the transmitting bridge is the root bridge. Each time, the bridge must compare 209-215 the received priority vector with the local PPV and immediately respond with a new BPDU identifying itself as the root bridge. At each step, the BPDUs are transmitted to downstream bridges all the way to bridge 120, thereby giving rise to a significant BPDU traffic burst. The burst only subsides only after the alternate port 111B of bridge 111 transmits a BPDU 210 identifying bridge 101 as the true root bridge. This BPDU identifying the proper root bridge is propagated to each of the bridges 112-120 and each bridge updates its root port information. As one skilled in the art will appreciate, proposal/agreement BPDUs (not shown) may continue to propagate through the network 100 in accordance with the RSTP protocol. As can be seen, the bridge 120 adjacent to the failed link 130A receives ten BPDUs in the BPDU traffic burst. In general, the minimum burst size experienced by a bridge is equal to the number of bridges between the root bridge 101 and the alternate bridge 111 in the direction of the failure.
The first version of Spanning Tree in the legacy 802.1D 1998 standard introduced a burst limiter to inhibit BPDU traffic burst like that described above. A port compliant with the RSTP standard keeps track of the number of BPDUs sent with a standard variable referred to as the “txCount,” which is incremented each time a BPDU is transmitted. A BPDU is not transmitted if the txCount reaches a given maximum called txHoldCount. The txCount number is also automatically decremented each second, thereby allowing the BPDU transmissions to resume at a later time. As such, a port is permitted to burst as quickly as possible until the txHoldCount is reached, and then transmit one BPDU maximum per second thereafter as long as txCount remains greater than or equal to txHoldCount.
Currently, the txHoldCount is permitted to range from one to ten, with a default value set to six. Since the number of BPDU that may be transmitted is correlated to number of nodes in the network, a relatively larger network increases the chances of one or more bridges reaching such a threshold. As a result, the time required for convergence can be delayed between one to several seconds as a function of the frequency with which the burst limiter is triggered. There is therefore a need for a system and method to restrict the number of BPDUs transmitted while enabling the network to converge as quickly as possible without undue delay resulting from the RSTP burst limiter.